/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.index;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

import mosdi.fa.Alphabet;
import mosdi.fa.GeneralizedString;
import mosdi.util.BitArray;
import mosdi.util.Iupac;
import mosdi.util.Log;


/** Suffix tree implementation that stores a reference to child nodes 
 *  explicitly for each node and each alphabet character. This implementation
 *  is fast but space inefficient. */
public class SuffixTree {
	/** Presently 3+alphabetsize. */
	private int nodeSize;
	private int[] string;
	private int alphabetSize;
	// data structure:
	// nodeSize*nodeIdx+0: start
	// nodeSize*nodeIdx+1: end
	// nodeSize*nodeIdx+2: count
	// nodeSize*nodeIdx+3: link to node for character 0
	// ...
	// string[start..end] is the edge label above current node
	// count is the number of suffixes that correspond to current node
	private int[] suffixTreeTable;
	/** Nodes of larger depth (i.e. number of characters from root to this node) are 
	 *  not constructed. */
	private int maxDepth;
	private List<NodeConstructionListener> nodeConstructionListeners;
	private int totalSequenceLength;
	private int sequenceCount;

	/** Creates an empty tree. The tree is not usable before
	 *  buildTree() has been called. */
	public SuffixTree() {
		this.totalSequenceLength = -1;
		this.sequenceCount = -1;
		this.nodeSize = -1;
		this.string = null;
		this.alphabetSize = -1;
		this.suffixTreeTable = null;
		this.nodeConstructionListeners = new LinkedList<NodeConstructionListener>();
	}
	
	/** Constructs suffix tree and in a write-only top-down manner as described 
	 *  in "Efficient implementation of layz suffix trees" by Giegerich, Kurtz, Stoye.
	 *  @param string The "string" over an integer alphabet. The last character must be -1.
	 *                Values of -1 in the middle of the text are interpreted as stoppers,
	 *                i.e. a suffix tree of multiple strings is constructed.
	 */
	public SuffixTree(int[] string, int alphabetSize) {
		this();
		this.maxDepth = string.length;
		buildTree(string, alphabetSize);
	}

	/** Constructs suffix tree and in a write-only top-down manner as described 
	 *  in "Efficient implementation of layz suffix trees" by Giegerich, Kurtz, Stoye.
	 *  @param string The "string" over an integer alphabet. The last character must be -1.
	 *                Values of -1 in the middle of the text are interpreted as stoppers,
	 *  @param maxDepth Only nodes that correspond to prefixes not longer than maxDepth
	 *                  are constructed.
	 */
	public SuffixTree(int[] string, int alphabetSize, int maxDepth) {
		this();
		buildTree(string, alphabetSize, maxDepth);
	}

	public interface NodeConstructionListener {
		/** Called once before the construction of the first node. 
		 *  @param maxNodeCount Upper bound for the number of nodes that will 
		 *                      be constructed.
		 */
		public void initialize(int maxNodeCount);
		/** Called whenever a suffix tree node has been constructed. The order of
		 *  calls corresponds to the node indices.
		 *  
		 *  @param suffixStartPositions Start position in the underlying string 
		 *                              of all suffixes represented by the node 
		 *                              just constructed.
		 *  @param lcp Length of the commen prefix represented by the constructed
		 *             node, i.e. the number of characters on the labels from root
		 *             to the constructed node.
		 */
		public void nodeConstructed(int[] suffixStartPositions, int lcp, int parentLcp);
		
		/** Called after all nodes have been constructed. */
		public void allNodesConstructed();
	}
	
	public void addNodeConstructionListener(NodeConstructionListener ncl) {
		nodeConstructionListeners.add(ncl);
	}
	

	/** Returns the number of suffix tree nodes. */
	public int getNodeCount() {
		assert suffixTreeTable.length%nodeSize == 0;
		return suffixTreeTable.length/nodeSize;
	}

	/** Returns the size of a suffix tree nodes in bytes. */
	public int getNodeSize() {
		return nodeSize*4;
	}
	
	public int getTotalSequenceLength() {
		return totalSequenceLength;
	}

	public int getSequenceCount() {
		return sequenceCount;
	}

	/** Constructs suffix tree and in a write-only top-down manner as described 
	 *  in "Efficient implementation of layz suffix trees" by Giegerich, Kurtz, Stoye.
	 *  @param string The "string" over an integer alphabet. The last character must be -1.
	 *                Values of -1 in the middle of the text are interpreted as stoppers,
	 *                i.e. a suffix tree of multiple strings is constructed.
	 *  @param maxDepth Only nodes that correspond to prefixes not longer than maxDepth
	 *                  are constructed.
	 */
	public void buildTree(int[] string, int alphabetSize, int maxDepth) {
		if (string[string.length-1]!=-1) throw new IllegalArgumentException("String must end on -1.");
		sequenceCount = 0;
		totalSequenceLength = 0;
		for (int c : string) {
			if (c==-1) sequenceCount+=1;
			else totalSequenceLength+=1;
		}
		Log.printf(Log.Level.DEBUG, "SuffixTree: building tree for joint string of length %,d (composed of %d sequences)%n", string.length, sequenceCount);
		this.maxDepth = maxDepth;
		this.string = string;
		this.alphabetSize = alphabetSize;
		this.nodeSize = 3 + alphabetSize;
		// assume worst case of number of nodes = 2*stringlength
		int maxNodes = 2*string.length;
		// try second (possibly better) estimate via maxDepth
		long n = 1;
		for (int i=1; i<=maxDepth; ++i) {
			n+=Math.pow(alphabetSize, i);
			if (n>=maxNodes) break;
		}
		if (n<maxNodes) maxNodes = (int)n;
		Log.printf(Log.Level.DEBUG, "SuffixTree: max. nodes: %,d%n", maxNodes);
		this.suffixTreeTable = new int[maxNodes*nodeSize];
		// next position to be written to suffixTreeTable
		int pos = 0;
		// array containing all suffixes (encoded as indices in s which point
		// to the suffixes' starting positions)
		int[] suffixes = new int[string.length];
		for (int i=0; i<suffixes.length; ++i) suffixes[i]=i;
		// build tree
		for (NodeConstructionListener ncl : nodeConstructionListeners) {
			ncl.initialize(maxNodes);
		}
		pos = evaluateNode(suffixes, 0, suffixes.length-1, pos, 0);
		for (NodeConstructionListener ncl : nodeConstructionListeners) {
			ncl.allNodesConstructed();
		}
		// copy table over to save space...
		int[] newSuffixTreeTable = new int[pos];
		System.arraycopy(suffixTreeTable, 0, newSuffixTreeTable, 0, pos);
		this.suffixTreeTable = newSuffixTreeTable;
		assert suffixTreeTable.length%nodeSize==0;
		Log.printf(Log.Level.VERBOSE, "SuffixTree has %,d nodes using %,d bytes%n", suffixTreeTable.length/nodeSize, suffixTreeTable.length*4);
//		for (int i=0; i<suffixTreeTable.length; ++i) {
//			if (i%7==0) Log.printEverything("===");
//			Log.printEverything(String.format("%d: %d", i, suffixTreeTable[i]));
//		}	
	}
	
	/** Constructs suffix tree and in a write-only top-down manner as described 
	 *  in "Efficient implementation of layz suffix trees" by Giegerich, Kurtz, Stoye.
	 *  @param string The "string" over an integer alphabet. The last character must be -1.
	 *                Values of -1 in the middle of the text are interpreted as stoppers,
	 *                i.e. a suffix tree of multiple strings is constructed.
	 */
	public void buildTree(int[] string, int alphabetSize) {
		buildTree(string,alphabetSize,string.length);
	}

	public static SuffixTree buildSuffixTree(Alphabet alphabet, List<String> sequences, boolean considerReverse) {
		int maxLength = 0;
		for (String s : sequences) maxLength = Math.max(maxLength, s.length()+1);
		return buildSuffixTree(alphabet, sequences, considerReverse, maxLength);
	}
	
	public static SuffixTree buildSuffixTree(Alphabet alphabet, List<String> sequences, boolean considerReverse, int maxDepth) {
		SuffixTree suffixTree;
		// total sequence length
		int sequenceLength = 0;
		for (String s : sequences) sequenceLength+=s.length();
		// assemble sequence ...
		int[] intSequence;
		if (considerReverse) {
			intSequence = new int[2*(sequenceLength+sequences.size())];
			int n = 0;
			for (String s : sequences) {
				for (int i=0; i<s.length(); ++i) {
					intSequence[n++]=alphabet.getIndex(s.charAt(i));
				}
				intSequence[n++]=-1;
				String revComp = Iupac.reverseComplementary(s);
				for (int i=0; i<s.length(); ++i) {
					intSequence[n++]=alphabet.getIndex(revComp.charAt(i));
				}
				intSequence[n++]=-1;
			}
		} else {
			intSequence = new int[sequenceLength+sequences.size()];
			int n = 0;
			for (String s : sequences) {
				for (int i=0; i<s.length(); ++i) {
					intSequence[n++]=alphabet.getIndex(s.charAt(i));
				}
				intSequence[n++]=-1;
			}
		}
		Log.startTimer();
		suffixTree = new SuffixTree(intSequence, alphabet.size(), maxDepth);
		Log.stopTimer("Build suffix tree");
		return suffixTree;
	}	

	/** Calculate lcp of a range of suffixes. */
	private int computeLcp(int[] suffixes, int lowerBound) {
		if (suffixes.length==0) return -1;
		if (suffixes.length==1) return string.length - suffixes[0];
		int lcp = lowerBound;
		while (true) {
			int k = suffixes[0]+lcp;
			if (k>=string.length) break;
			int c = string[k];
			// stopper symbol never matches anything
			if (c<0) break; 
			int i=1;
			for (; i<suffixes.length; ++i) {
				k=suffixes[i]+lcp;
				if (k>=string.length) break;
				if (string[k]!=c) break;
			}
			if (i<suffixes.length) break;
			++lcp;
		}
		return lcp;		
	}
	
	/** Recursively creates nodes that correspond to suffixes found in 
	 *  the interval [p..q] in the array suffixes and writes them to 
	 *  suffixes, starting at position pos.
	 *  @param parentDepth Number of characters on labels between root and the 
	 *                     parent node.
	 *  @return Returns the next free position in array suffixes.
	 */
	private int evaluateNode(int[] suffixes, int p, int q, int pos, int parentDepth) {
		int[] currentSuffixes = Arrays.copyOfRange(suffixes, p, q+1);
		int lcp = computeLcp(currentSuffixes,parentDepth);
		// 1) write first part of nodes (without links)
		suffixTreeTable[pos++]=currentSuffixes[0]+parentDepth;
		suffixTreeTable[pos++]=currentSuffixes[0]+lcp-1;
		suffixTreeTable[pos++]=currentSuffixes.length;
		if ((p==q) || (lcp>=maxDepth)) {
		// if (p==q) {
			// current node is a leaf
			// the empty references to child nodes could be omitted 
			// to save space, but matching is (a bit) easier with them...
			for (int i=0; i<alphabetSize; ++i) suffixTreeTable[pos++]=-1;
			// Notify possible listeners that a node has been constructed
			for (NodeConstructionListener ncl : nodeConstructionListeners) {
				ncl.nodeConstructed(currentSuffixes, lcp, parentDepth);
			}
		} else {
			// current node is not a leaf
			// 2) stable sort the interval [p..q] according to the suffixes' first letter
			//   a) count the letters occuring at the first positions of suffixes in question
			int[] letterFrequencies = new int[alphabetSize];
			for (int i : currentSuffixes) {
				int c = string[i+lcp];
				// ignore stop characters
				if (c>=0) letterFrequencies[c]+=1;	
			}
			//   b) calculate positions to place suffixes starting with a certain character
			int[] positions = new int[alphabetSize];
			for (int i=1; i<positions.length; ++i) {
				positions[i]=positions[i-1]+letterFrequencies[i-1];	
			}
			//   c) sort from currentSuffixes into array suffixes
			for (int i : currentSuffixes) {
				int c = string[i+lcp];
				if (c>=0) suffixes[p+positions[c]++]=i;
			}
			// 3) Notify possible listeners that a node has been constructed
			for (NodeConstructionListener ncl : nodeConstructionListeners) {
				ncl.nodeConstructed(currentSuffixes, lcp, parentDepth);
			}
			// 4) recurse on subnodes and write references
			int refPos = pos;
			// reserve space for references
			pos+=alphabetSize;
			int start = p;
			for (int i=0; i<alphabetSize; ++i) {
				if (letterFrequencies[i]==0) {
					suffixTreeTable[refPos++]=-1;
				} else {
					suffixTreeTable[refPos++]=pos;
					int end = start+letterFrequencies[i]-1;
					pos = evaluateNode(suffixes, start, end, pos, lcp);
					start = end+1;
				}
			}
		}
		return pos;
	}
	
	/** Returns the index of the node that corresponds to the given
	 *  pattern. If pattern could not be found, -1 is returned. */
	public int getNodeIndex(int[] pattern) {
		if (suffixTreeTable==null) throw new IllegalStateException("No tree has been constructed.");
		SuffixTreeWalker walker = getWalker();
		int[] activeNodes = null; 
		for (int c : pattern) {
			activeNodes = walker.forward(c);
			if (activeNodes.length==0) return -1;
		}
		assert(activeNodes.length==1);
		return activeNodes[0];
	}
	
	public int[] getNodeIndex(GeneralizedString gs) {
		if (suffixTreeTable==null) throw new IllegalStateException("No tree has been constructed.");
		SuffixTreeWalker walker = getWalker();
		int[] activeNodes = null; 
		for (BitArray c : gs.getPositions()) {
			activeNodes = walker.forward(c);
		}
		return activeNodes;
	}

	/** Counts the number of times the given string matches the text 
	 *  underlying this suffix tree. */
	public int countMatches(int[] pattern) {
		int index = getNodeIndex(pattern);
		if (index<0) return 0;
		return suffixTreeTable[index*nodeSize+2];
	}

	/** Counts the number of times the given generalized string matches the text 
	 *  underlying this suffix tree.
	 *  @param gs A generalized string that is to be searched for. */
	public int countMatches(GeneralizedString gs) {
		int matches = 0;
		for (int nodeIndex : getNodeIndex(gs)) {
			matches += suffixTreeTable[nodeIndex*nodeSize+2];
		}
		return matches;
	}

	/** Recursively processes the tree in pre-order and annotates each node 
	 *  with the length of the path from root to this node. The result is stored
	 *  in the array "annotations". */
	private void pathLengthAnnotation(int node, int parent, int[] annotations) {
		int pos = nodeSize*node;
		if (parent>=0) {
			annotations[node]=annotations[parent]+(suffixTreeTable[pos+1]-suffixTreeTable[pos]+1);
		} else {
			annotations[node]=suffixTreeTable[pos+1]-suffixTreeTable[pos]+1;
		}
		for (int i=0; i<alphabetSize; ++i) {
			if (suffixTreeTable[pos+3+i]<0) continue;
			pathLengthAnnotation(suffixTreeTable[pos+3+i]/nodeSize, node, annotations);
		}
	}
	
	private void calcMaxMatchCountAnnotationRecursive(int node, int patternLength, int[] pathLengths, int[] matchCountAnnotations) {
		int pos = nodeSize*node;
		for (int i=0; i<alphabetSize; ++i) {
			if (suffixTreeTable[pos+3+i]<0) continue;
			calcMaxMatchCountAnnotationRecursive(suffixTreeTable[pos+3+i]/nodeSize, patternLength, pathLengths, matchCountAnnotations);
		}
		if (pathLengths[node]>=patternLength) {
			matchCountAnnotations[node]=suffixTreeTable[pos+2];
		} else {
			int n = 0;
			for (int i=0; i<alphabetSize; ++i) {
				int childPos = suffixTreeTable[pos+3+i];
				if (childPos<0) continue;
				n=Math.max(n, matchCountAnnotations[childPos/nodeSize]);
			}
			matchCountAnnotations[node]=n;
		}
	}
	
	/** Calculates an annotation for each node that gives the maximal possible
	 *  number of matches of a pattern (of given length) whose prefix 
	 *  is the label from root to the current node.
	 */
	public int[] calcMaxMatchCountAnnotation(int patternLength) {
		if (suffixTreeTable==null) throw new IllegalStateException("No tree has been constructed.");
		int[] nodeDepths = new int[suffixTreeTable.length/nodeSize];
		pathLengthAnnotation(0, -1, nodeDepths);
		int[] matchCountAnnotation = new int[suffixTreeTable.length/nodeSize];
		calcMaxMatchCountAnnotationRecursive(0, patternLength, nodeDepths, matchCountAnnotation);
		return matchCountAnnotation;
	}
	
	/** Recursively processes the smallTree (i.e. the suffix tree of one (not all) sequences
	 *  that are in the whole tree) and, in parallel, the whole tree. For each node in the small
	 *  tree, add sequenceIdx to the annotation that corresponds to the current 
	 *  node of the whole tree.
	 */
	private void sequenceOccurrenceAnnotation(int node, SuffixTree smallTree, int smallTreePos, int sequenceIdx, BitArray[] annotations) {
		annotations[node].set(sequenceIdx, true);
		int pos = nodeSize*node;
		for (int i=0; i<alphabetSize; ++i) {
			int newSmallTreePos = smallTree.suffixTreeTable[smallTreePos+3+i]; 
			if (newSmallTreePos<0) continue;
			// find corresponding node in whole tree by walking along the edge-label ...
			// new node in whole tree
			int newPos = suffixTreeTable[pos+3+i];
			// edge label position in whole tree (we skip first character)
			int edgeLabelPos = suffixTreeTable[newPos]+1; 
			for (int j=smallTree.suffixTreeTable[newSmallTreePos]+1; j<=smallTree.suffixTreeTable[newSmallTreePos+1]; ++j) {
				int c = smallTree.string[j];
				if (c<0) break;
				if (edgeLabelPos<=suffixTreeTable[newPos+1]) {
					// just advance on edgelabel
					if (c!=string[edgeLabelPos]) throw new IllegalStateException("Edge-label do not match. This is a BUG!");
					edgeLabelPos+=1;
				} else {
					// there exists an intermediate node in the whole tree, tag it and advance ...
					annotations[newPos/nodeSize].set(sequenceIdx, true);
					newPos = suffixTreeTable[newPos+3+c];
					if (newPos<0) throw new IllegalStateException("Node does not exist. This is a BUG!");
					edgeLabelPos = suffixTreeTable[newPos]+1;
				}
			}
			sequenceOccurrenceAnnotation(newPos/nodeSize, smallTree, newSmallTreePos, sequenceIdx, annotations);
		}
	}
	
	/** Calculates an annotation for each node that tells in which sequences (of possibly
	 *  multiple sequences seperated by -1 characters) the current prefix can be found.
	 *  
	 *  @param groupSize If groupSize is 1, then each sequences is treated separately; if 
	 *                   >1, then groupSize number of sequences are joined. The case 
	 *                   groupSize =2 is useful to simultaneously treat a sequence an its 
	 *                   reverse.
	 */
	public BitArray[] calcSequenceOccurrenceAnnotation(int groupSize) {
		if (suffixTreeTable==null) throw new IllegalStateException("No tree has been constructed.");
		// could be done more efficient if incorporated into tree creation process
		// here, we build a suffix tree for each single sequence
		// 1) split sequences
		List<int[]> sequences = new ArrayList<int[]>();
		int k = 0;
		int start = 0;
		for (int i=0; i<string.length; ++i) {
			if (string[i]<0) {
				k+=1;
				if (k==groupSize) {
					int[] s = new int[i-start+1];
					System.arraycopy(string, start, s, 0, i-start+1);
					sequences.add(s);
					start=i+1;
					k=0;
				}
			}
		}
		if (k!=0) throw new IllegalArgumentException("Number of sequences must be divisible by groupSize!");
		// 2) create array for results
		BitArray[] annotations = new BitArray[suffixTreeTable.length/nodeSize];
		for (int i=0; i<annotations.length; ++i) annotations[i] = new BitArray(sequences.size()); 
		// 3) for each sequence, build suffix tree and record the existance of each node
		//    (which means that the current prefix is contained in current sequence) in the
		//    appropriate annotation
		int n = 0;
		for (int[] s : sequences) {
			SuffixTree smallTree = new SuffixTree(s, alphabetSize);
			this.sequenceOccurrenceAnnotation(0, smallTree, 0, n++, annotations);	
		}
		return annotations;
	}
	
	/** Return for each node the number of occurrences of the string corresponding
	 *  to the respective node.
	 */
	public int[] calcOccurrenceCountAnnotation() {
		if (suffixTreeTable==null) throw new IllegalStateException("No tree has been constructed.");
		int nodeCount = suffixTreeTable.length/nodeSize;
		int[] annotation = new int[nodeCount];
		for (int i=0; i<nodeCount; ++i) {
			annotation[i] = suffixTreeTable[i*nodeSize+2];
		}
		return annotation;
	}
	
	/** Auxilliary class used by Walker. */
	private class PositionData {
		// number of suffix tree nodes to be considered (may increase due to
		// ambiguity in given generalized string)
		int capacity;
		int size;
		// array of positions (suffix tree nodes) to be considered
		int[] positions;
		// edgeLabelPositions[k] contains the current position on
		// the edgeLabel above node positions[k].
		// edgeLabelPositions[k]=-1 indicates that the complete edge-label has
		// been processed.
		int[] edgeLabelPositions;
		int[] nodeIndices;
		PositionData(int capacity) {
			this.capacity = capacity;
			size = 0;
			positions = new int[capacity];
			edgeLabelPositions = new int[capacity];
			nodeIndices = null;
		}
		void add(int position, int edgeLabelPosition) {
			if (size>=capacity) throw new IndexOutOfBoundsException();
			positions[size]=position;
			edgeLabelPositions[size]=edgeLabelPosition;
			size+=1;
			nodeIndices = null;
		}
		int[] getNodeIndices() {
			if (nodeIndices==null) {
				nodeIndices = new int[size];
				for (int i=0; i<size; ++i) nodeIndices[i]=positions[i]/nodeSize;
			}
			return nodeIndices;
		}
	}
	
	private class Walker implements SuffixTreeWalker {
		/** Contains the nodes that were active after each forward step
		 *  performed in the past. (i.e. history.length-1 equals the length
		 *  of the current pattern). */
		Stack<PositionData> history;
		
		private Walker() {
			history = new Stack<PositionData>();
			PositionData pd = new PositionData(1);
			pd.add(0,-1);
			history.push(pd);
		}
		
		@Override
		public int[] backward(int charactersToKeep) {
			while (history.size()>charactersToKeep+1) history.pop();
			return history.peek().getNodeIndices();
		}

		/** Performs one step from all positions given in oldPositions and adds the new
		 *  positions to newPositions. */
		private void step(int character, PositionData oldPositions, PositionData newPositions) {
			for (int i=0; i<oldPositions.size; ++i) {
				// is whole edge label "used up"?
				if (oldPositions.edgeLabelPositions[i]==-1) {
					// if yes, proceed to child node (if existant)
					int pos = suffixTreeTable[oldPositions.positions[i]+3+character];
					if (pos>=0) {
						int edgeLabelPosition;
						if (suffixTreeTable[pos]<suffixTreeTable[pos+1]) {
							// edge label with more than one character
							edgeLabelPosition=suffixTreeTable[pos]+1;
						} else {
							// one character edge label
							edgeLabelPosition=-1;
						}
						newPositions.add(pos, edgeLabelPosition);
					}
				} else {
					// if no, walk along edge label
					int labelPos = oldPositions.edgeLabelPositions[i];
					int pos = oldPositions.positions[i];
					if (string[labelPos]==character) {
						// ok, characters match, store new position
						newPositions.add(pos, (labelPos<suffixTreeTable[pos+1])?labelPos+1:-1);
					} 
				}
			}
		}
		
		@Override
		public int[] forward(BitArray generalizedChar) {
			PositionData oldPositions = history.peek();
			PositionData newPositions = new PositionData(oldPositions.size*alphabetSize);
			for (int c=0; c<alphabetSize; ++c) {
				if (!generalizedChar.get(c)) continue;
				step(c, oldPositions, newPositions);
			}
			history.push(newPositions);
			return newPositions.getNodeIndices();
		}

		@Override
		public int[] forward(int character) {
			PositionData oldPositions = history.peek();
			PositionData newPositions = new PositionData(oldPositions.size);
			step(character, oldPositions, newPositions);
			history.push(newPositions);
			return newPositions.getNodeIndices();
		}
	}
	
	public SuffixTreeWalker getWalker() {
		if (suffixTreeTable==null) throw new IllegalStateException("No tree has been constructed.");
		return new Walker();
	}

	/** Walk along the suffix tree as specified in a given pattern.
	 *  @return Returns the active nodes after this walk.
	 */
	public int[] walk(GeneralizedString gs) {
		if (suffixTreeTable==null) throw new IllegalStateException("No tree has been constructed.");
		SuffixTreeWalker walker = getWalker();
		int[] nodeIndices = {0};
		for (int i=0; i<gs.length(); ++i) {
			nodeIndices = walker.forward(gs.getPosition(i));
		}
		return nodeIndices;
	}

	/** Walk along the suffix tree as specified in a given pattern.
	 *  @return Returns the active nodes after this walk.
	 */
	public int[] walk(int[] pattern, BitArray[] generalizedAlphabet) {
		if (suffixTreeTable==null) throw new IllegalStateException("No tree has been constructed.");
		SuffixTreeWalker walker = getWalker();
		int[] nodeIndices = {0};
		for (int i=0; i<pattern.length; ++i) {
			nodeIndices = walker.forward(generalizedAlphabet[pattern[i]]);
		}
		return nodeIndices;
	}

}
 
